public class DSU {
    //先写一个非递归版本的
    //靠 小挂大 和 扁平化 牛客版本的并查集
    //https://www.nowcoder.com/practice/e7ed657974934a30b2010046536a5372
    public static int set = 1000000;
    public static int[] farther = new int[set + 1];
    public static int[] size = new int[set + 1];
    public static int[] stack = new int[set + 1];
    public void build(int n){
        for (int i = 1; i <= n; i++) {
            farther[i] = i;
            size[i] = 1;
        }
    }
    public int find(int n){
        int t = 0;
        while(farther[n] != n){
            stack[t++] = n;
            n = farther[n];
        }
        while(t != 0){
            farther[stack[--t]] = n;
        }
        return n;
    }
    public boolean isSameSet(int a, int b){
        return find(a) == find(b);
    }


    public void union(int a,int b){
        int fa = find(a);
        int fb = find(b);
        if(fa != fb){
            if(size[fa] < size[fb]){
                farther[fa] = fb;
                size[fb] += size[fa];
            }else{
                farther[fb] = fa;
                size[fa] += size[fb];
            }
        }
    }
}
